Student Instructions | Week 6 | Topics: Bisection, Newton-Raphson, convergence
Oregon State University | ENGR 103 | Dr. Cheng Li
Last week you used exhaustive search to approximate square roots. It took thousands of steps. Today we'll find the same answer in under 50 steps using bisection.
Type and run this code:
eps = 0.01
x = 2.0
low, high, n = 0, 2, 0
while abs(high - low) > 2 * eps:
mid = (low + high) / 2
if mid**2 < x:
low = mid
else:
high = mid
n += 1
print(f'√2 ≈ {(low + high) / 2:.8f} in {n} steps')Run it. How many steps did it take? How does this compare to last week's exhaustive approach (~14,000 steps for the same problem)?
Type and run each snippet.
Bisection works by repeatedly halving the search interval. At each step, compute the midpoint and keep whichever half still contains a sign change. Type and run this code:
# Find sqrt(7) using bisection: solve x^2 - 7 = 0 on [0, 7]
# f(0) = -7 (negative), f(7) = 42 (positive) → sign change confirmed
lo = 0.0
hi = 7.0
eps = 1e-8
steps = 0
while abs(hi - lo) > 2 * eps and steps < 200:
mid = (lo + hi) / 2
f_mid = mid**2 - 7
f_lo = lo**2 - 7
if f_mid * f_lo < 0:
hi = mid
else:
lo = mid
steps += 1
root = (lo + hi) / 2
print(f'√7 = {root:.10f} (true: {7**0.5:.10f}) in {steps} steps')Modify the code above to find the cube root of 50 (i.e., solve x³ − 50 = 0). Use the interval [0, 50]. What is f_mid and f_lo for the cube root version? How many steps does it take?
Use bisection to find the positive root of x² − 9 = 0, then compare to the exact answer. Type and run this code:
# Find root of x^2 - 9 = 0 on [1, 5] using bisection
# f(1) = 1 - 9 = -8 (negative), f(5) = 25 - 9 = 16 (positive)
lo = 1.0
hi = 5.0
eps = 1e-8
steps = 0
while abs(hi - lo) > 2 * eps and steps < 200:
mid = (lo + hi) / 2
f_mid = mid**2 - 9
f_lo = lo**2 - 9
if f_mid * f_lo < 0:
hi = mid
else:
lo = mid
steps += 1
x_bisect = (lo + hi) / 2
x_exact = 3.0
print(f'Bisection: x = {x_bisect:.10f} ({steps} steps)')
print(f'Exact: x = {x_exact:.10f}')
print(f'Error: {abs(x_bisect - x_exact):.2e}')Change the code to find the root of x² − 25 = 0 on [1, 6]. What is the exact answer? How many steps does bisection take?
Newton-Raphson improves a guess using the tangent line: x_new = x − f(x)/f'(x). Type and run this code:
# Newton-Raphson for sqrt(2): solve f(x) = x^2 - 2 = 0
# f'(x) = 2x
x = 1.5 # initial guess
eps = 1e-12
steps = 0
converged = False
for i in range(50):
fx = x**2 - 2
dfx = 2 * x
if abs(dfx) < 1e-15:
print('Derivative too small — stopping')
break
xn = x - fx / dfx
steps += 1
if abs(xn - x) < eps:
x = xn
converged = True
break
x = xn
if converged:
print(f'√2 (Newton) = {x:.15f} in {steps} steps')
print(f'√2 (true) = {2**0.5:.15f}')
else:
print('Did not converge')How many steps does Newton-Raphson take? Compare to bisection (Exercise 6A warm-up: ~10 steps) and last week's exhaustive search (~14,000 steps). What do you notice about Newton-Raphson's speed?
Work in pairs. The polynomial f(x) = x³ − 4x² + x + 6 has three real roots: x = −1, x = 2, and x = 3. Use bisection to find all three roots, then apply Newton-Raphson to one of them and compare step counts.
Type and run this code to verify the three roots:
# Polynomial: f(x) = x^3 - 4x^2 + x + 6
# Verify: f(-1), f(2), f(3) should all equal 0
for x_check in [-1, 2, 3]:
f_val = x_check**3 - 4*x_check**2 + x_check + 6
print(f'f({x_check:>2}) = {f_val:.3f}')Run the verification. Do all three values equal 0.000?
Use the starter code below. A for loop supplies three bracketing intervals; a while
loop inside performs bisection for each one.
intervals = [(-2.0, 0.0), (1.5, 2.5), (2.5, 4.0)]
eps = 1e-8
print(f'{"Interval":>15} | {"Root found":>12} | {"f(root)":>10} | {"Steps":>6}')
print('-' * 52)
for lo_start, hi_start in intervals:
lo = lo_start
hi = hi_start
steps = 0
while abs(hi - lo) > 2 * eps and steps < 200:
mid = (lo + hi) / 2
f_mid = mid**3 - 4*mid**2 + mid + 6
f_lo = lo**3 - 4*lo**2 + lo + 6
if f_mid * f_lo < 0:
hi = mid
else:
lo = mid
steps += 1
root = (lo + hi) / 2
f_root = root**3 - 4*root**2 + root + 6
print(f'[{lo_start}, {hi_start}] | {root:>12.8f} | {f_root:>10.2e} | {steps:>6d}')
# Extension: Newton-Raphson for the root near x = 3
# f(x) = x^3 - 4x^2 + x + 6
# f'(x) = 3x^2 - 8x + 1
x_nr = 3.5 # initial guess
eps_nr = 1e-12
steps_nr = 0
converged = False
for i in range(50):
fx = x_nr**3 - 4*x_nr**2 + x_nr + 6
dfx = 3*x_nr**2 - 8*x_nr + 1
if abs(dfx) < 1e-15:
break
xn = x_nr - fx / dfx
steps_nr += 1
if abs(xn - x_nr) < eps_nr:
x_nr = xn
converged = True
break
x_nr = xn
if converged:
print(f'\nNewton-Raphson root near 3: x = {x_nr:.10f} in {steps_nr} steps')
else:
print('Newton-Raphson did not converge')For √N where N = 2, 10, 100, 1000: compare step counts for exhaustive (step=0.001), bisection, and Newton-Raphson. All three methods use only while and for loops — no functions needed.
Type and run this code:
results = []
for x in [2, 10, 100, 1000]:
# --- Bisection for sqrt(x): solve t^2 - x = 0 on [0, x] ---
lo, hi, nb = 0.0, float(x), 0
while abs(hi - lo) > 2e-8 and nb < 300:
mid = (lo + hi) / 2
if mid**2 < x:
lo = mid
else:
hi = mid
nb += 1
# --- Newton-Raphson for sqrt(x): t_new = (t + x/t) / 2 ---
v, nn = float(x) / 2, 0
for _ in range(100):
vn = (v + x / v) / 2
nn += 1
if abs(vn - v) < 1e-12:
break
v = vn
# --- Exhaustive estimate (step = 0.001) ---
ne_est = int(x**0.5 / 0.001)
results.append((x, nb, nn, ne_est))
print(f"{'x':>6} {'Bisect':>8} {'Newton':>8} {'Exhaust~':>10}")
for x, nb, nn, ne in results:
print(f'{x:>6} {nb:>8d} {nn:>8d} {ne:>10,}')Run it. What pattern do you see in the Newton-Raphson column? Why does bisection's step count increase while Newton-Raphson's stays nearly constant?
Show TA your Part 2 table (three roots found via bisection, plus the Newton-Raphson step count). Discuss: when would you prefer bisection over Newton-Raphson?